package medium;

import javax.print.attribute.HashAttributeSet;
import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/12/14 0:24
 */
public class No56_合并区间 {
    public static void main(String[] args) {
        Solution56 solution56 = new Solution56();
        int[][] intervals = new int[][]{
                {1, 2},
                {3, 6},
                {5, 8},
                {4, 5},
                {3, 9}
        };
        int[][] merge = solution56.merge(intervals);
        System.out.println(merge);
    }
}

class Solution56 {
    public int[][] merge(int[][] intervals) {
        //list
        List<List<Integer>> dataList = new ArrayList<>();
        
        //数组搞成list
        for (int[] interval : intervals) {
            List<Integer> data = new ArrayList<>();
            data.add(interval[0]);
            data.add(interval[1]);
            dataList.add(data);
        }
        
        //自定义排序
        //注意:Comparison method violates its general contract! 一般注意不到
        dataList.sort(new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                //[3,6][3,9]
                if (o1.get(0) > o2.get(0)) {
                    return 1;
                } else if (o1.get(0) < o2.get(0)) {
                    return -1;
                } else if (o1.get(0) == o2.get(0)) {
                    return 0;
                }else {
                    return o1.get(1) < o2.get(1) ? -1 : 1;
                } 
            }
        });

        //开始合并
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < dataList.size(); i++) {
            mergeList(res, dataList.get(i));
        }
        
        //搞回数组
        int[][] resInts = new int[res.size()][2];
        for (int i = 0; i < res.size(); i++) {
            resInts[i][0] = res.get(i).get(0);
            resInts[i][1] = res.get(i).get(1);
        }

        return resInts;
    }

    //合并list方法
    public void mergeList(List<List<Integer>> res, List<Integer> data) {

        if (res.size() == 0) {
            res.add(data);
            return;
        }
        
        //将data合并进res
        
        //获取x,y
        int x = res.get(res.size() - 1).get(0);
        int y = res.get(res.size() - 1).get(1);

        int a = data.get(0);
        int b = data.get(1);
        
        //按规律进行合并
        if (a >= x && a <= y && b > y) {
            //(x,b)
            res.remove(res.size() - 1);
            data.clear();
            data.add(x);
            data.add(b);
            res.add(data);
        } else if (a >= x && a <= y && b <= y) {
            //(x,y)
            res.remove(res.size() - 1);
            data.clear();
            data.add(x);
            data.add(y);
            res.add(data);
        } else if (a > y) {
            res.add(data);
        }
        
    }
}



    //public int[][] merge(int[][] intervals) {
    //    // 强行硬写!!!!
    //    
    //    //使用TreeMap将同一起始点放一起,方便合并
    //    TreeMap<Integer, List<List<Integer>>> treeMap = new TreeMap<>();
    //    
    //    //遍历数组
    //    for (int[] interval : intervals) {
    //        //获取起始点
    //        int key = interval[0];
    //        //将同一起始点map化
    //        if (treeMap.get(key) == null) {
    //            treeMap.put(key, new ArrayList<>());
    //        }
    //        treeMap.get(key).add(new ArrayList<>(Arrays.asList(interval[0], interval[1])));
    //    }
    //
    //    //遍历map,合并多个区间
    //
    //    for (Map.Entry<Integer, List<List<Integer>>> treeMapData : treeMap.entrySet()) {
    //        //3-> {3,6},{3,9}
    //        int key = treeMapData.getKey();
    //        //value合并
    //        //将最大值赋值给check,然后扔之check即可
    //        int check = 0;
    //        
    //        //{3,6},{3,9}
    //        List<List<Integer>> value = treeMapData.getValue();
    //        for (int i = 0; i < value.size(); i++) {
    //            if (value.get(i).get(1) > check) {
    //                check = value.get(i).get(1);
    //            }
    //        }
    //        value.clear();
    //        //坑,如果直接ArrayList New 后面get(0)会出bug,大坑...
    //        value.add(new ArrayList<>(Arrays.asList(key, check)));
    //        
    //        //check一定最大,扔:{key,check}
    //        treeMap.put(key, value);
    //
    //    }
    //
    //    //2->{{1,2}}
    //    //3->{{3,9}}
    //    
    //    //接下来开始对treeMap进行遍历,开始最后一波合并
    //    //{1,2}{3,9}{4,5}{5,8}合并
    //    
    //    //最终结果list
    //    List<List<Integer>> resList = new ArrayList<>();
    //    
    //    //开始合并
    //    for (Map.Entry<Integer, List<List<Integer>>> mapData : treeMap.entrySet()) {
    //        int key = mapData.getKey();
    //        mergeList(resList, mapData.getValue().get(0));//{{}}
    //    }
    //
    //
    //    //扔回数组
    //    int[][] res = new int[resList.size()][2];
    //    for (int i = 0; i < resList.size(); i++) {
    //        res[i][0] = resList.get(i).get(0);
    //        res[i][1] = resList.get(i).get(1);
    //        
    //    }
    //
    //    return res;
    //    
    //}
    //
    ////合并list方法
    //public void mergeList(List<List<Integer>> res, List<Integer> data) {
    //
    //    if (res.size() == 0) {
    //        res.add(data);
    //        return;
    //    }
    //    
    //    //将data合并进res
    //    
    //    //获取x,y
    //    int x = res.get(res.size() - 1).get(0);
    //    int y = res.get(res.size() - 1).get(1);
    //
    //    int a = data.get(0);
    //    int b = data.get(1);
    //    
    //    //按规律进行合并
    //    if (a >= x && a <= y && b > y) {
    //        //(x,b)
    //        res.remove(res.size() - 1);
    //        data.clear();
    //        data.add(x);
    //        data.add(b);
    //        res.add(data);
    //    } else if (a >= x && a <= y && b <= y) {
    //        //(x,y)
    //        res.remove(res.size() - 1);
    //        data.clear();
    //        data.add(x);
    //        data.add(y);
    //        res.add(data);
    //    } else if (a > y) {
    //        res.add(data);
    //    }
    //    
    //}